Spectral radius of finite and infinite planar graphs and of graphs of bounded genus

摘要

It is well known that the spectral radius of a tree whose maximum degree is$D$ cannot exceed $2\sqrt{D-1}$. In this paper we derive similar bounds forarbitrary planar graphs and for graphs of bounded genus. It is proved that athe spectral radius $\rho(G)$ of a planar graph $G$ of maximum vertex degree$D\ge 4$ satisfies $\sqrt{D}\le \rho(G)\le \sqrt{8D-16}+7.75$. This result isbest possible up to the additive constant--we construct an (infinite) planargraph of maximum degree $D$, whose spectral radius is $\sqrt{8D-16}$. Thisgeneralizes and improves several previous results and solves an open problemproposed by Tom Hayes. Similar bounds are derived for graphs of bounded genus.For every $k$, these bounds can be improved by excluding $K_{2,k}$ as asubgraph. In particular, the upper bound is strengthened for 5-connectedgraphs. All our results hold for finite as well as for infinite graphs. At the end we enhance the graph decomposition method introduced in the firstpart of the paper and apply it to tessellations of the hyperbolic plane. Wederive bounds on the spectral radius that are close to the true value, and evenin the simplest case of regular tessellations of type $\{p,q\}$ we derive anessential improvement over known results, obtaining exact estimates in thefirst order term and non-trivial estimates for the second order asymptotics.